import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class StringAlgorithm {

    @Test
    public void sameChars() {
        // 字符串A和B中，字符种类和每种字符出现的次数是否相同
        String a = "hello world ";
        String b = "hell world o";

        int[] temp = new int[256];
        if (a.equals(b)) {
            Assertions.assertTrue(true);
        } else if (a.length() != b.length()) {
            Assertions.assertTrue(false);
        } else {
            for (int i = 0; i < a.length(); i++) {
                temp[a.charAt(i)]++;
                temp[b.charAt(i)]--;
            }

            for (int i = 0; i < temp.length; i++) {
                if (temp[i] != 0) {
                    Assertions.assertTrue(false);
                }
            }
        }

    }

    @Test
    public void loopString() {
        //找出是否从A串的循环中可以读到B串
        String a = "12345";
        String b = "23451";

        String temp = a + a;
        Assertions.assertTrue(temp.contains(b));

    }

    @Test
    public void rotateWord() {
        char[] chars = "dog loves pig".toCharArray();
        reversWord(chars, 0, chars.length - 1);

        int left = -1;
        int right = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                if (i == 0 || chars[i-1]==' ') {
                    left = i;
                }

                if (i == chars.length - 1 || chars[i + 1] == ' ') {
                    right = i;
                }

                if (left != -1 && right != -1) {
                    reversWord(chars, left, right);
                    left = -1;
                    right = -1;
                }
            }
        }

        Assertions.assertEquals(String.valueOf(chars), "pig loves dog");
    }

    private void reversWord(char[] chars, int left, int right) {
        char temp;
        int i = left;
        int j = right;

        while (i < j) {
            temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;

            i++;
            j--;
        }
    }

    @Test
    public void findSmallest() {
        String[] strs = {"ab", "b", "a", "ccc"};//找到最小的合并串
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        System.out.println(sb);
    }

    @Test
    public void findSubStr() {
        //找出字符串中的最长两个相同子串
        String str = "abcxxababcd";

        int maxLen = 0;
        int begin1 = 0;
        int begin2 = 0;
        char[] chars = str.toCharArray();
        int lastIndex = chars.length - 1;
        int curLen ;
        for (int i = 0; i < chars.length - maxLen && i < lastIndex ; i++) {
            for (int j = i+1; j < chars.length - maxLen && j <= lastIndex; j++) {
                curLen = 0;
                for (int m = i, n = j; m <= lastIndex && n <= lastIndex; m++, n++) {//如果排序数组，则可以减少比较次数，只需要比较相邻的串
                    if (str.charAt(m) == str.charAt(n)) {
                        curLen++;
                    } else {
                        break;
                    }
                }
                System.out.println(i+","+j+","+curLen);
                if (curLen > maxLen) {
                    maxLen = curLen;
                    begin1 = i;
                    begin2 = j;
                }
            }
        }
        Assertions.assertEquals(maxLen ,3);//abc
        Assertions.assertEquals(begin1 ,0);
        Assertions.assertEquals(begin2 ,7);
    }

    @Test
    public void findMaxCommonSubStr() {
        //找两个串的最大公共子串
        String stra = "advkjsdlkjlwetrlkzxm";
        String strb = "sdfjijwokjzxcnfkjwetrhru";

        int[][] dp = new int[stra.length()][strb.length()];
        int max = 0;
        for (int i = 0; i < stra.length(); i++) {
            for (int j = 0; j < strb.length(); j++) {
                if (stra.charAt(i) == strb.charAt(j)) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        System.out.println(max);
    }

    /**
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     *
     * s = "leetcode"
     返回 0.
     s = "loveleetcode",
     返回 2.
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        int[] temp = new int[256];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = -1;
        }
        for (int i = 0; i < s.length(); i++) {
            if (temp[s.charAt(i)] == -1) {
                temp[s.charAt(i)] = i;
            } else {
                temp[s.charAt(i)] = -2;
            }
        }

        int min = -1;
        for (int position : temp) {
            if (position >= 0 && (min < 0 || min > position)) {
                min = position;
            }
        }
        return min;
    }

    @Test
    public void testFindLongestWord(){
        String s = "aewfafwafjlwajflwajflwafj";
        String[] d = {"apple", "ewaf", "awefawfwaf", "awef", "awefe", "ewafeffewafewf"};
        String result = findLongestWord(s, Arrays.asList(d));
        Assertions.assertEquals(result, "ewaf");

    }

    /**
     * Given a string and a string dictionary, find the longest string
     * in the dictionary that can be formed by deleting some characters of the given string.
     * If there are more than one possible results,
     * return the longest word with the smallest lexicographical order.
     * If there is no possible result, return the empty string.
     */
    public String findLongestWord(String s, List<String> d) {
        int max = -1;
        String result = "";
        for(String str: d) {
            if(str.length() > max || (str.length() == max && result.compareTo(str) > 0 )) {
                boolean isContain = true;
                int indexOfChar = -1;
                for(int i=0;i<str.length();i++){
                    indexOfChar = s.indexOf(str.charAt(i), indexOfChar + 1);
                    if (indexOfChar == -1) {
                        isContain = false;
                        break;
                    }
                }
                if (isContain) {
                    max = str.length();
                    result = str;
                }
            }
        }

        return result;
    }
}
